/* 
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。


输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
输出：-1
说明: 不存在返回-1。


思路：双指针的变形，先判断是否为空字符串，
*/
/**
 * @param {string[]} words
 * @param {string} s
 * @return {number}
 */
 var findString = function(words, s) {
    let left = 0
    let right = words.length - 1
    while (left <= right) {
        let mid_bak = mid = (left + right) >> 1
        // 重点：对空字符串的处理，除了mid右移以外，还要处理右侧超出边界的问题
        while (mid <= right && !words[mid]) {
            mid++;
        }
        // console.log(left, mid, right)
        // 右侧超出边界后压缩边界
        if (mid > right) {  // 若mid超出右边界(即为右边界+1), 说明mid至right处都为空字符串
            right = mid_bak - 1; // 压缩右边界至mid_bak的位置
            continue;   // 进行下一次循环
        }
        if (words[mid] > s) {
            // 去左数组查找
            right = mid - 1
        } else if (words[mid] < s) {
            // 去右数组查找
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
};

let words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"

let res=findString(words, s)
console.log(res);